#Genome Assembly as Shortest Superstring(寻找最小的超字符窜)
import os
os.chdir('C:/Users/admin/Desktop')
seq_list = []
#提取所有的序列部分
with open('25_Genome_Assembly_as_Shortest_Superstring.txt','r') as fp:
    for line in fp:
        if line[0] != '>':
            seq_list.append(line.strip())
def MergeMaxOverlap(str_list):
    max_length = -1
    #错位匹配
    for prefix_index in range(len(str_list)):
        for suffix_index in [num for num in range(len(str_list)) if num != prefix_index]:
            prefix,suffix = str_list[prefix_index], str_list[suffix_index]
            i= 0
            while prefix[i:] != suffix[0:len(prefix[i:])]:
                i += 1
            if len(prefix) - i > max_length:
                max_length = len(prefix) - i
                max_indicies = [prefix_index, suffix_index]
    return ([str_list[j] for j in range(len(str_list)) if j not in max_indicies] + 
            [str_list[max_indicies[0]] + 
             str_list[max_indicies[1]][max_length:]])
def LongestCommonSuperstring(str_list):
    while len(str_list) >1:
        str_list = MergeMaxOverlap(str_list)
    return str_list[0]

if __name__ == '__main__':
    dna_list = [i for i in seq_list]
    super_string = LongestCommonSuperstring(dna_list)
    print(super_string)
